package com.zjj.lbw.algorithm.adt;

/**
 * @author zhanglei.zjj
 * @description leetcode_200. 岛屿数量
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：grid = [
 * ["1","1","1","1","0"],
 * ["1","1","0","1","0"],
 * ["1","1","0","0","0"],
 * ["0","0","0","0","0"]
 * ]
 * 输出：1
 * 示例 2：
 * <p>
 * 输入：grid = [
 * ["1","1","0","0","0"],
 * ["1","1","0","0","0"],
 * ["0","0","1","0","0"],
 * ["0","0","0","1","1"]
 * ]
 * 输出：3
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 300
 * grid[i][j] 的值为 '0' 或 '1'
 * @date 2023/6/12 20:47
 */
public class NumberofIslands_leetcode_200 {
    public int numIslands(char[][] grid) {
        L200_ADT adt = new L200_ADT(grid);
        int m = grid.length;
        int n = grid[0].length;
        // 遍历原始数组中的每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 检测右侧是否连通，连通则要合并
                    if (j < n - 1 && grid[i][j + 1] == '1') {
                        adt.union(i * n + j, i * n + j + 1);
                    }
                    // 检测下侧是否连通，连通则要合并
                    if (i < m - 1 && grid[i + 1][j] == '1') {
                        adt.union(i * n + j, i * n + j + n);
                    }
                }
            }
        }

        return adt.isLandsCount - adt.mergeCount;
    }
}

class L200_ADT {
    // 存储每个元素的父结点
    private int[] parents;
    // 原始数组元素为二维char，转为一维int，rank的作用记录每个结点的子树深度
    // 因为在两棵树合并时，把小树合并到大树上，可以让每个元素到根结点的距离最少
    private int[] rank;

    // 初始岛屿数量
    public int isLandsCount = 0;
    // 合并数量
    public int mergeCount = 0;

    public L200_ADT(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        parents = new int[m * n];
        rank = new int[m * n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    isLandsCount++;
                    // 初始每个元素的父结点都是自身
                    parents[i * n + j] = i * n + j;
                    // 初始每个元素的子树深度为1
                    rank[i * n + j] = 1;
                }
            }
        }
    }

    // 带路径压缩的查找父结点
    public int find(int child) {
        // 集合中只有根结点的父节点是自己
        if (parents[child] == child) {
            return child;
        }
        // 树自然可以递归处理，并且在查询的过程中不断变更节点的父节点,以缩短查找路径
        return parents[child] = find(parents[child]);
    }

    // 合并集合
    public void union(int childA, int childB) {
        int parentA = find(childA);
        int parentB = find(childB);
        // 两个子树根结点不一致，进行集合合并
        if (parentA != parentB) {
            // 合并次数+1
            mergeCount++;
            // 把小树合并到大树上面
            if (rank[childA] >= rank[childB]) {
                parents[parentB] = parentA;
            } else {
                parents[parentA] = parentB;
            }

            // 两棵树深度一样，深度要+1
            if (rank[parentA] == rank[parentA]) {
                rank[parentA]++;
            }
        }
    }
}
